public class Solution12 {
    static String[] romaChar;

    static String[] specChar;

    static {
        romaChar=new String[4000];
        romaChar[1]="I";
        romaChar[5]="V";
        romaChar[10]="X";
        romaChar[50]="L";
        romaChar[100]="C";
        romaChar[500]="D";
        romaChar[1000]="M";

        specChar=new String[4000];
        specChar[4]="IV";
        specChar[9]="IX";
        specChar[40]="XL";
        specChar[90]="XC";
        specChar[400]="CD";
        specChar[900]="CM";
    }

    public int findSmaller(int num){
        for (int i = num; i >= 0 ; i--) {
            if(romaChar[i]!=null){
                return i;
            }
        }
        return -1;
    }

    public String findProbStr(int num){
        if(specChar[num]!=null){return specChar[num];}

        StringBuilder result=new StringBuilder();
        while(num!=0){
            int ind=findSmaller(num);
            result.append(romaChar[ind]);
            num-=ind;
        }
        return result.toString();
    }

    public String intToRoman(int num) {
        StringBuilder totalRes=new StringBuilder();
        String strNum=Integer.toString(num);
        double rate=Math.pow(10,(strNum.length()-1));
        for (int i = 0; i < strNum.length(); i++) {
            int tmpNum=(int)((strNum.charAt(i)-'0')*Math.max(rate,1));
            totalRes.append(findProbStr(tmpNum));
            rate=rate/10;
        }
        return totalRes.toString();
    }
}
